class Node:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.parent = None


class Solution(object):
    def flipBinaryTree(self, root, leaf):
        """
        :type node: Node
        :rtype: Node
        """
        def dfs(node):
            if node == leaf:
                node.parent = None
                return True, node
            if node.left:
                left_flag, left_tree = dfs(node.left)
                if left_flag:
                    left_tree.left = node
                    node.left = None
                    node.parent = left_tree
                    return True, node
            if node.right:
                right_flag, right_tree = dfs(node.right)
                if right_flag:
                    right_tree.left = node
                    if node.parent:
                        node.right = node.left
                        node.left = None
                    else:
                        node.right = None
                    node.parent = right_tree
                    return True, node
            return False, node
        dfs(root)
        return leaf

